﻿//2271. 毯子覆盖的最多白色砖块数
//给你一个二维整数数组 tiles ，其中 tiles[i] = [li, ri] ，表示所有在 li <= j <= ri 之间的每个瓷砖位置 j 都被涂成了白色。
//同时给你一个整数 carpetLen ，表示可以放在 任何位置 的一块毯子的长度。
//请你返回使用这块毯子，最多 可以盖住多少块瓷砖。


class Solution {
public:
    int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen)
    {
        sort(tiles.begin(), tiles.end(), [](auto a, auto b) { return a[0] < b[0]; });
        int left = 0;
        int n = tiles.size();
        int ans = 0;
        int cnt = 0;
        int right = 0;
        //枚举毯子起始位置
        for (left = 0; left < n; left++)
        {
            if (left)
            {
                cnt -= tiles[left - 1][1] - tiles[left - 1][0] + 1;
            }
            while (right < n && (tiles[left][0] + carpetLen > tiles[right][1]))
            {
                cnt += tiles[right][1] - tiles[right][0] + 1;
                right++;
            }


            if (right == n)
            {
                ans = max(ans, cnt);
                return ans;
            }
            int s = max(0, tiles[left][0] + carpetLen - tiles[right][0]);

            ans = max(cnt + s, ans);
        }
        return ans;
    }
};